/**
 * @Author Fizz Pu
 * @Date 2020/11/10 下午7:35
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

/**
 * 最长公共子序列问题
 */

public class Lee1143 {
    public int longestCommonSubsequence(String text1, String text2) {
            if(text1 == null || text2 == null){
                throw  new  IllegalArgumentException();
            }

            int lenText1 = text1.length(), length2 = text2.length();
            int[][] dp = new int[lenText1 + 1][length2 + 1];

            //默认已经初始化

            for(int row = 1; row <= lenText1; ++row){
                for(int col = 1; col <= length2; ++col){
                    if(text1.charAt(row-1) == text2.charAt(col-1)){
                        dp[row][col] = 1 + dp[row-1][col];
                    } else {
                        dp[row][col] = Math.max(dp[row-1][col], dp[row][col-1]);
                    }
                }
            }

            return dp[lenText1][length2];
    }

    public static void main(String[] args) {
        Lee1143 lee = new Lee1143();
        System.out.println(lee.longestCommonSubsequence("abcde", "ace") == 3);
        System.out.println(lee.longestCommonSubsequence("abc", "abc") == 3);
        System.out.println(lee.longestCommonSubsequence("abc", "def") == 0);
        System.out.println(lee.longestCommonSubsequence("", "def") == 0);
        System.out.println(lee.longestCommonSubsequence("", "") == 0);
    }
}
